Removal and amalgamation

Abstract: The key step in the proof of the triangle removal lemma can be viewed as saying that we can identify a small number of edges in a graph as being the "exceptional" edges, and the remaining edges are sufficiently "representative of the neighborhood around them" that, if there are any triangles left, there must have been many triangles. This can be viewed as a amalgamation problem in the sense of model-theory: given types p(x,y), q(x,z), and r(y,z), each of which indicates that there is an edge between the vertices, when are the types p,q,r "large" in a way which guarantees that there are many (x,y,z) extending each of these types?

The exceptional types can be characterized as the non-Lebesgue points - that is, the points which fail to satisfy the Lebesgue density theorem in the right measure space. We give a way to generalize this to types of higher arity and use this to prove a new generalization, an "ordered hypergraph removal lemma", extending the recent ordered graph removal lemma of Alon, Ben-Eliezer, and Fischer.

logic

Audience: researchers in the topic

UCLA logic colloquium